﻿#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:6031)

#include <stdio.h>
#include <string.h>

//int main(void)
//{
//	char str_1[] = "abc";
//	char str_2[] = "abc";
//	char str_3[] = "ABC";
//	if (strcmp(str_1, str_2) == 0)
//		printf("str_1 is equal to str_2. \n");
//	else
//		printf("str_1 is not equal to str_2. \n");
//	if (strcmp(str_1, str_3) == 0)
//		printf("str_1 is equal to str_3．\n");
//	else
//		printf("str_1 is not equal to str_3．\n");
//	
//	int fanhuizhi1 = strcmp(str_1, str_2);
//	printf("%d\n", fanhuizhi1);
//
//	int fanhuizhi2 = strcmp(str_1, str_3);
//	printf("%d\n", fanhuizhi2);
//
//	return 0;
//}

/* memset example */
//int main()
//{
//	char str[] = "almost every programmer should know memset!";
//	memset(str+7, '-', 5);		
//	/*puts(str);*/
//	printf("%s\n", str);
//	return 0;
//}

/*写⼀个加法函数，完成2个整型变量的加法操作*/
//int Add(int x, int y)		//定义了Add函数，⽽不去调⽤的话，Add函数的参数 x,y称为形式参数
//{
//	int z = x + y;
//	return z;
//}
//
//int main()
//{
//	int a = 0;
//	int b = 0;
//	scanf("%d %d", &a, &b);
//	int sum=Add(a, b);		//调⽤Add函数时，传递给函数的参数a和b，称为实际参数，简称实参。
//	printf("%d\n", sum);
//
//	return 0;
//}

/*写一个函数可以交换两个整型变量的内容*/
/*B站P39*/
//void Swap(int x, int y)		//两个变量交换的话需要第三个变量
//{
//	int z = 0;
//	z = x;
//	x = y;
//	y = z;
//}
//
//int main()
//{
//	int a = 0;
//	int b = 0;
//	scanf("%d %d", &a, &b);
//	printf("交换前：a=%d b=%d\n", a, b);
//	Swap(a, b);		//传值调用
//	printf("交换后：a=%d b=%d\n", a, b);
//
//	return 0;
//}

//代码有问题，通过调试解决bug//
//当实参传递给形参的时候，形参是实参的一份临时拷贝，会有自己独立的空间；对形参（x，y）的修改不会影响实参(a,b)

/*修改前————————修改后*/

//int main()
//{
//	int a = 10;
//	int* p=&a;	//取出a的地址放到指针变量p中
//	a = 20;	//直接改
//	*p = 30;	//间接改；*p就是a
//	
//	return 0;
//}

//void Swap(int* px, int* py)		//指针变量接收地址
//{
//	int z = 0; 
//	z = *px;		//*px就是a；*py就是b
//	*px = *py;
//	*py = z;
//}
//
//int  main()
//{
//	int a = 0;
//	int b = 0;
//	scanf("%d %d", &a, &b);
//	printf("交换前：a=%d b=%d\n", a, b);
//	Swap(&a, &b);		//&a，&b是两个实参；传址调用
//	printf("交换后：a=%d b=%d\n", a, b);
//
//	return 0;
//}

//思考：在上面的加法函数中为什么在调用Add函数时没有传地址？什么情况下在传参数的时候要传地址
//当要改变实参的值或者对实参做出变化时需要用到指针，所以要传地址——传址调用
//不用对实参的值进行改变就可完成代码功能，不需要传地址——传值调用（函数的形参和实参分别占有不同内存块，对形参的修改不会影响实参。）
//注：形参和实参的名字可以相同，也可以不同

 //练习4.3
/*1.1用循环判断一个数是否是素数*/
/*若不能将此自然数写成比它自己小的自然数的乘积，就称为素数（由0、1、质数构成）*/
/*质数：2，3，5，7，11...*/

/*	sqrt函数:计算平⽅根
 1 double sqrt(double x);
 2 sqrt 是函数名
 3 x 是函数的参数，表⽰调⽤sqrt函数需要传递⼀个double类型的值
 4 double 是返回值类型 - 表⽰函数计算的结果是double类型的值
*/

//#include <math.h>
//
//int main(void)
//{
//	double x = 4;
//	double i = sqrt(x);
//	printf("%.1lf\n", i);		//%lf接收double类型的数据，%.1lf就是小数点后保留一位
//
//	return 0;
//}

//#include <math.h>		//sqrt
//
//int main()	
//{
//	int i = 0;
//	int count = 0;
//	
//	for (i = 101; i <= 200; i+=2)		//偶数一定不是素数，所以可以先把范围缩小到奇数
//	{
//		int flag = 1;	//每次循环前都让flag初始化为1表示是素数；此方法用标志位进行判断
//		int j = 0;		//用i对2~i-1之间的数字不断取余
//
//		for (j = 2; j <= sqrt(i); j++)		//j <= i - 1
//		{
//			if (i % j == 0)		//余数为0就代表可以被整除，i不是素数，立马跳出循环
//			{
//				flag = 0;
//				break;			//满足条件就直接跳出for循环
//			}	
//		}
//		if (flag == 1)		//若flag为1就说明i不能被j整除，i是素数，可以打印
//		{
//			count++;
//			printf("%d ", i);
//		}
//	}
//	printf("\n一共有%d个素数\n", count);
//
//	return 0;
//}

//优化代码：若一个数不是素数，那其两个乘数中一定有一个数<=这个数的算术平方根
//所以j <= sqrt(i)即可，减少了遍历次数
//还可以继续优化：偶数一定不是素数，所以可以从101开始，i+=2，从所有奇数中判断是不是素数


/*1.2写一个函数判断一个数是否是素数；调试：B站1:18:00*/

//#include <math.h>		//数学库函数
// 
//int is_prime(int n)		//是素数就返回1，不是素数就返回0
//{
//	int j = 0;
//
//	for (j = 2; j <= sqrt(n); j++)		//j <= i - 1
//	{
//		if (n % j == 0)		//余数为0就代表可以被整除，i不是素数就返回0
//		{
//			return 0;		//只要return，这个函数就结束了；break只是跳出for循环
//		}
//	}
//	
//	return 1;
//}
//
//int main()
//{
//	int i = 0;
//	int count = 0;
//
//	for (i = 101; i <= 200; i +=2)		//首先产生100~200中间的奇数
//	{
//		if ( 1==is_prime(i) )
//		{
//			printf("%d ", i);
//			count++;
//		}
//	}
//	printf("\ncount=%d\n", count);
//
//	return 0;
//}

//布尔类型：布尔型（bool）变量的值只有真（true)和假（false）。C99标准才引入

//#include <math.h>		//sqrt
//#include <stdbool.h>	//bool
//
//bool is_prime(int n)		//是素数就返回1，不是素数就返回0
//{
//	int j = 0;
//
//	for (j = 2; j <= sqrt(n); j++)		//j <= i - 1
//	{
//		if (n % j == 0)		//余数为0就代表可以被整除，i不是素数就返回0
//		{
//			return false;		//只要return，这个函数就结束了；break只是跳出for循环
//		}
//	}
//
//	return true;
//}
//
//int main()
//{
//	int i = 0;
//	int count = 0;
//
//	for (i = 101; i <= 200; i += 2)		//首先产生100~200中间的奇数
//	{
//		if (is_prime(i))
//		{
//			printf("%d ", i);
//			count++;
//		}
//	}
//	printf("\ncount=%d\n", count);
//
//	return 0;
//}


/*2.打印1000~2000年之间的闰年*/
//闰年：能被4整除、但不能被100整除，或能被400整除的年份为闰年；这两种判断方法才能找全闰年；其余为平年。

//int main()
//{
//	int i = 0;
//	int count = 0;
//
//	for (i = 1000; i <= 2000; i ++ )
//	{
//		if (i % 4 == 0 && i % 100 != 0)
//		{
//			printf("%d ", i);
//			count++;
//		}
//		if (i % 400 == 0)		//不能写else if，这两种规则都要判断
//		{
//			printf("%d ", i);
//			count++;
//		}
//	}
//	printf("\n一共有%d个闰年\n", count);
//	return 0;
//}

//优化

//int is_leap_year(int n)
//{
//	if (((n % 4 == 0) && (n % 100 != 0)) || (n % 400 == 0))
//	{
//		return 1;
//	}
//	else
//	{
//		return 0;
//	}
//}
//
//int main()
//{
//	int i = 0;
//	int count = 0;
//	
//	for (i = 1000; i <= 2000; i++)
//	{
//		if (1 == is_leap_year(i))
//		{
//			printf("%d ", i);
//			count++;
//		}
//	}
//
//	printf("\n一共有%d个闰年\n", count);
//	return 0;
//}


/*3.1 在一个有序数组中查找具体的某个数字n。（讲解二分查找）*/
//sizeof计算的是类型所占空间的的大小（字节）；%zu打印sizeof的返回值
//sizeof(arr)计算的是整个数组所占空间的大小，因为1个整形占4个字节，若数组中有10个元素就占40个字节
//sizeof(arr[0])计算的是第一个元素类型的大小
//strlen(arr1)计算的是字符串长度（\0之前的字符串长度）

//遍历数组
//int main()
//{
//	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
//	int k = 7;		//在上面的有序数组中找数字7
//	int i = 0;
//	int sz = sizeof(arr)/sizeof(arr[0]);		//计算数组中的元素个数
//	for (i = 0; i < sz; i++)		
//	{
//		if (arr[i] == k)
//		{
//			printf("找到了，下标是%d", i);
//			break;
//		}
//	}
//	if (i == sz)
//	{
//		printf("找不到");
//	}
//	return 0;
//}

//优化：二分查找（但只适应于有序数组）
//int main()
//{
//	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
//	int k = 7;		//在上面的有序数组中找数字7
//	int sz = sizeof(arr) / sizeof(arr[0]);		//计算数组中的元素个数		
//	
//	int left = 0;		//定义左下标-0
//	int right = sz-1;	//定义右下标-9
//	
//	while (left <= right)
//	{
//		//int mid = (left + right) / 2;		//这种写法当left+right超过整形的范围时会有溢出的问题
//		int mid = left + (right - left) / 2;//确定中间的下标-4；4对应元素的为5，然后5与7相比；
//
//		if (arr[mid] < k)		//说明要找的元素在5的右边；左下标left要改成mid+1
//		{
//			left = mid + 1;
//		}
//		else if (arr[mid] > k)	//说明要找的元素在5的左边；右下标right要改成mid-1
//		{
//			right = mid - 1;
//		}
//		else 
//		{
//			printf("找到了，下标是%d", mid);
//			break;
//		}
//	}
//	if (left > right)
//	{
//		printf("找不到");
//	}
//
//	return 0;
//} 

/*3.2写一个函数实现一个整形有序数组的二分查找*/
//int binary_search(int arr[], int k, int sz)		//此处的形参arr本质上是一个指针变量，存的是实参数组传过来的首元素地址；数组传参实际上传递的是数组首元素的地址，而不是整个数组
//{												//不能在此函数中计算一个数组当中的元素个数，所以不能把计算数组中的元素个数的代码放在这里
//	int left = 0;		//定义左下标-0
//	int right = sz-1;	//定义右下标-9
//	
//	while (left <= right)
//	{
//		//int mid = (left + right) / 2;		//这种写法当left+right超过整形的范围时会有溢出的问题
//		int mid = left + (right - left) / 2;//确定中间的下标-4；4对应元素的为5，然后5与7相比；
//
//		if (arr[mid] < k)		//说明要找的元素在5的右边；左下标left要改成mid+1
//		{
//			left = mid + 1;
//		}
//		else if (arr[mid] > k)	//说明要找的元素在5的左边；右下标right要改成mid-1
//		{
//			right = mid - 1;
//		}
//		else
//		{
//			return mid;			//找到了就返回下标mid
//		}
//	}
//
//	return -1;
//}
//
//int main()
//{
//	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
//	int k = 7;		//在上面的有序数组中找数字7
//	int sz = sizeof(arr) / sizeof(arr[0]);		//计算数组中的元素个数		
//	
//	int ret = binary_search(arr, k, sz);	//需要传递三个参数，在arr数组里的所有元素中查k
//											//找到了返回下标mid，找不到可以返回-1
//	if (ret == -1)
//	{
//		printf("找不到");
//	}
//	else
//	{
//		printf("找到了，下标是%d\n", ret);
//	}
//
//	return 0;
//}

//写代码思路：先想好这个函数怎么用，再实现函数的定义，此时函数的参数，返回类型等就比较清晰


/*4. 写一个函数，每调用一次这个函数，就会将 num 的值增加1。*/

//void add(int* n)		
//{
//	(*n)++;
//}
//
//int main()
//{
//	int num = 0;
//	add(&num);		//当要改变实参的值或者对实参做出变化时需要用到指针，所以要传地址——传址调用；传值也可以实现功能
//	printf("%d\n",num);		//1
//	add(&num);
//	printf("%d\n", num);	//2
//	add(&num);	
//	printf("%d\n", num);	//3
//	add(&num);
//	printf("%d\n", num);	//4
//
//	return 0;
//}


/*5. 函数的嵌套调用和链式访问*/
//5.1嵌套调用
//void new_line()
//{
//	printf("hehe\n");
//}
//void three_line()
//{
//	int i = 0;
//	for (i = 0; i < 3; i++)
//	{
//		new_line();
//	}
//}
//int main()
//{
//	three_line();
//	return 0;
//}

//函数可以嵌套调用，但是不能嵌套定义。定义的函数里面不能再定义另一个函数

//5.2链式访问：把一个函数的返回值作为另外一个函数的参数。
//#include <string.h>		//strlen,strcat

//int main()
//{
//	char arr[20] = "hello";
//	int ret = strlen(strcat(arr, "bit"));		//将strcat的返回值作为strlen的参数
//	printf("%d\n", ret);
//	return 0;
//}

//int main()
//{
//	printf("%d", printf("%d", printf("%d", 43)));		//先会在屏幕上打印43，返回值为2作为中间printf的参数
//	//结果是啥？——4321
//	//注：printf函数的返回值是打印在屏幕上字符的个数
//	return 0;
//}


/*6. 函数的声明和定义*/

//#pragma comment(lib,"add.lib")		//导入静态库

//#include "add.h"		//add		
//#include "sub.h"		//sub		
//
//int main()
//{
//	int a = 0;
//	int b = 0;
//	scanf("%d %d", &a, &b);
//
//	int sum = add(a, b);
//	printf("%d\n", sum);
//
//	int ret = sub(a, b);
//	printf("%d\n", ret);
//
//	return 0;
//}

/*7. 函数递归*/
//递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
//把大事化小

/*练习*/
//7.1.接受一个整型值（无符号），按照顺序打印它的每一位。
//例如：
//输入：1234，输出 1 2 3 4.

//%d是打印有符号的正数（会有正负数）
//%u是打印无符号的正数

//输⼊⼀个正的整数，逆序打印这个整数的每⼀位，但不是顺序打印
//int main()
//{
//	int i = 0;
//	scanf("%d", &i);
//
//	while (i)
//	{
//		printf("%d ", i % 10);	//对10取余就可得到最低位，打印最低位
//		i /= 10;				//除10就可去掉最低位，下一次打印就会打印倒数第二位
//	}
//	return 0;
//}

//递归的实现方法	B站P46 19:50-画图讲解

//void print(unsigned int n)		//调用此函数就能把num的每一位打印在屏幕上
//{
//	if (n > 9)		//若n为1234；若不加if判断就会栈溢出：Stack overflow
//	{
//		print(n / 10);		//此处就打印123
//	}
//	printf("%d ", n % 10);	//此处就打印4
//}
//
//int main()
//{
//	unsigned int num = 0;
//	scanf("%u", &num);		
//	print(num);		//封装print函数，它的功能就是按照顺序打印每一位。
//
//	return 0;
//}

//每一次的函数调用都会在栈区申请空间，所以连续不停的调用函数就会一直向栈区申请空间，直到栈溢出

//递归的两个必要条件
//1.存在限制条件，当满足这个限制条件的时候，递归便不再继续。【if (n > 9)】
//2.每次递归调用之后越来越接近这个限制条件。【n / 10】


/*7.2 编写函数不允许创建临时变量，求字符串的长度。*/
//模拟实现strlen

//int my_strlen(char* str)		//接收字符a的地址，所以为char*； str指向a；参数部分写成指针的形式
//{								//注意my_strlen中的参数写成char str[]也可；参数部分写成数组的形式
//	int count = 0;		//count就是临时变量
//	while (*str != '\0')		//*str就是字符a
//	{
//		count++;
//		str++;		//找下一个字符
//	}
//
//	return count;
//}

 //递归的实现

//int my_strlen(char* str)		//接收字符a的地址，所以为char*； str指向a；参数部分写成指针的形式
//{								//注意my_strlen中的参数写成char str[]也可；参数部分写成数组的形式
//	if (*str != '\0')
//	{
//		return 1 + my_strlen(str+1);
//	}
//	else
//	{
//		return 0;
//	}
//}
//
//int main()
//{
//	char arr[] = "abcd";
//	int len = my_strlen(arr);			//注意传的是a的地址
//	printf("%d\n", len);
//
//	return 0;
//}


/* 7.3 递归与迭代*/
// 7.3.1求n的阶乘
// n!=1*2*3*...*n——循环（迭代的一种）

//int fac(int n)
//{
//	int i = 0;
//	int ret = 1;
//	for (i = 1; i <= n; i++)
//	{
//		ret = ret * i;
//	}
//	return ret;
//}

// 公式：fac(n)=n!=		  1      （n<=1）
//			          n*fac(n-1) （n >1）——递归
// 
//int fac(int n)
//{
//	if (n <= 1)
//		return 1;
//	else
//		return n * fac(n - 1);
//}
//
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int ret = fac(n);
//	printf("%d\n", ret);
//
//	return 0;
//}

//7.3.2 求第n个斐波那契数。
//斐波那契数列
//1 1 2 3 5 8 13 21 34 55 ...
//公式：Fib(n)=      1	（n<=2）
//					Fib(n-1)+ Fib(n - 2)	(n>2)

//int Fib(int n)
//{
//	if (n <= 2)
//		return 1;
//	else
//		return Fib(n - 1) + Fib(n - 2);
//}
//
//int main()
//{
//	int n = 0;
//	scanf ("%d", &n);
//	int ret = Fib(n);
//	printf("%d\n", ret);
//
//	return 0;
//}

//缺点：会存在大量重复的计算，效率低下；可用迭代的方法

int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;

	while (n >= 3)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}

	return c;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d\n", ret);

	return 0;
}

